{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #验证图书取出顺序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validateBookSequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证图书取出顺序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现在图书馆有一堆图书需要放入书架，并且图书馆的书架是一种特殊的数据结构，只能按照 <strong>一定</strong> 的顺序 <strong>放入</strong> 和 <strong>拿取</strong> 书籍。</p>\n",
    "\n",
    "<p>给定一个表示图书放入顺序的整数序列 <code>putIn</code>，请判断序列 <code>takeOut</code> 是否为按照正确的顺序拿取书籍的操作序列。你可以假设放入书架的所有书籍编号都不相同。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>putIn = [6,7,8,9,10,11], takeOut = [9,11,10,8,7,6]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>我们可以按以下操作放入并拿取书籍：\n",
    "push(6), push(7), push(8), push(9), pop() -&gt; 9,\n",
    "push(10), push(11),pop() -&gt; 11,pop() -&gt; 10, pop() -&gt; 8, pop() -&gt; 7, pop() -&gt; 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>putIn = [6,7,8,9,10,11], takeOut = [11,9,8,10,6,7]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>6 不能在 7 之前取出。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= putIn.length == takeOut.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= putIn[i], takeOut &lt; 1000</code></li>\n",
    "\t<li><code>putIn</code> 是 <code>takeOut</code> 的排列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 946 题相同：<a href=\"https://leetcode-cn.com/problems/validate-stack-sequences/\">https://leetcode-cn.com/problems/validate-stack-sequences/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zhan-de-ya-ru-dan-chu-xu-lie-lcof](https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zhan-de-ya-ru-dan-chu-xu-lie-lcof](https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,7,8,9,10,11]\\n[9,11,10,8,7,6]', '[6,7,8,9,10,11]\\n[11,9,8,10,6,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                # 在putin的最后一次遍历会尝试stack.pop出所有元素，若无法全部pop出则False\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for x in putIn:\n",
    "            stack.append(x)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        if len(takeOut)==0:\n",
    "            return True\n",
    "        \n",
    "        shelf=[]\n",
    "\n",
    "        for t_id in takeOut:\n",
    "            if t_id in putIn:\n",
    "                idx=putIn.index(t_id)\n",
    "                shelf+=putIn[0:idx]\n",
    "                putIn=putIn[idx+1:]\n",
    "            else: \n",
    "                if t_id != shelf[-1]:\n",
    "                    return False\n",
    "                else:\n",
    "                    shelf.pop()\n",
    "        return True\n",
    "                \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        heaq = []\n",
    "        i = 0\n",
    "        for n in putIn:\n",
    "            heaq.append(n)\n",
    "            while len(heaq) != 0 and heaq[-1] == takeOut[i]:\n",
    "                i += 1\n",
    "                heaq.pop()\n",
    "        return len(heaq) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = collections.deque()\n",
    "        outIdx = 0\n",
    "        for x in putIn:\n",
    "            while stack:\n",
    "                if takeOut[outIdx] == stack[-1]:\n",
    "                    stack.pop()\n",
    "                    outIdx += 1\n",
    "                else:\n",
    "                    break\n",
    "            if x == takeOut[outIdx]:\n",
    "                outIdx += 1\n",
    "            else:\n",
    "                stack.append(x)\n",
    "\n",
    "        # print(stack)\n",
    "        \n",
    "        for j in range(outIdx, len(takeOut)):\n",
    "            if not stack:\n",
    "                return False\n",
    "            x = stack.pop()\n",
    "            if takeOut[j] != x:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and takeOut[i] == stack[-1]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        res, k = [], 0\n",
    "        for i in putIn:\n",
    "            res.append(i)\n",
    "            while 1:\n",
    "                if res and takeOut[k] == res[-1]:\n",
    "                    k += 1\n",
    "                    res.pop()\n",
    "                else:\n",
    "                    break\n",
    "        return not res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        sk,i=[],0\n",
    "        for num in putIn:           \n",
    "            sk.append(num)            \n",
    "            while sk and  sk[-1]==takeOut[i]:\n",
    "                sk.pop()\n",
    "                i+=1\n",
    "        return not sk\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        st = []\n",
    "        i = 0\n",
    "        for x in putIn:\n",
    "            while st and st[-1] == takeOut[i]:\n",
    "                st.pop()\n",
    "                i += 1\n",
    "            st.append(x)\n",
    "        while st and st[-1] == takeOut[i]:\n",
    "                st.pop()\n",
    "                i += 1\n",
    "        return i == len(takeOut)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(takeOut)\n",
    "        helps = []  \n",
    "        moni = [] \n",
    "        i = 0\n",
    "        for in_num in putIn:\n",
    "            helps.append(in_num)   #模拟入栈\n",
    "            while helps and i <= n-1 and helps[-1] == takeOut[i]:\n",
    "                moni.append(helps.pop())  #模拟出栈\n",
    "                i += 1\n",
    "        return moni == takeOut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        st,j = [],0\n",
    "        for num in putIn:\n",
    "            st.append(num)\n",
    "            while st and st[-1] == takeOut[j]:\n",
    "                st.pop()\n",
    "                j += 1\n",
    "        return st == []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack,i  = [],0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        j=0\n",
    "        for i in putIn:\n",
    "            stack.append(i)\n",
    "            if i !=takeOut[j]:\n",
    "                continue\n",
    "            else:\n",
    "                while stack and stack[-1]==takeOut[j]:\n",
    "                    stack.pop()\n",
    "                    j+=1\n",
    "        return  not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack,i = [],0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i +=1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        puti = 0\n",
    "        takei = 0\n",
    "        for i in putIn:\n",
    "            stack.append(i)\n",
    "            while len(stack)>0 and stack[-1] == takeOut[0]:\n",
    "                takeOut.pop(0)\n",
    "                stack.pop()\n",
    "\n",
    "\n",
    "        #takeOut.reverse()\n",
    "        if len(stack) == 0 :\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        valid_left = 0\n",
    "        valid_right = len(putIn)\n",
    "    \n",
    "        try:\n",
    "            for out_id in takeOut:\n",
    "                # print(f'find {out_id}, valid_left {valid_left}')\n",
    "                i = putIn.index(out_id, valid_left)\n",
    "                valid_left = i - 1 if i - 1 > 0 else 0                \n",
    "                del putIn[i]\n",
    "                # print(f'i:{i}, valid:{putIn[valid_left:]}, putIn:{putIn}')\n",
    "        except:\n",
    "            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        j = 0\n",
    "        for i in putIn:\n",
    "            stack.append(i)\n",
    "            while stack and stack[-1] == takeOut[j]:\n",
    "                stack.pop()\n",
    "                j += 1\n",
    "        if not stack:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n, m = len(putIn), len(takeOut)\n",
    "        if n!=m: return False\n",
    "\n",
    "        stack = []\n",
    "        pin, pout = 0, 0\n",
    "        while pout<n:\n",
    "            if not stack or (pin<n and stack[-1]!=takeOut[pout]):\n",
    "                stack.append(putIn[pin])\n",
    "                pin+=1\n",
    "            elif stack[-1]==takeOut[pout]:\n",
    "                stack.pop()\n",
    "                pout+=1\n",
    "            else: return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        idx = 0\n",
    "        for i in putIn:\n",
    "            stack.append(i)\n",
    "            while stack and stack[-1] == takeOut[idx]:\n",
    "                stack.pop()\n",
    "                idx += 1\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        temp = []\n",
    "        index = 0\n",
    "        for num in putIn:\n",
    "            temp.append(num)\n",
    "            while temp and takeOut[index] == temp[-1]:\n",
    "                temp.pop()\n",
    "                index += 1\n",
    "        return True if not temp else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        book=[]\n",
    "        p2=0\n",
    "        for p1 in range(len(putIn)):\n",
    "            book.append(putIn[p1])\n",
    "            while book and book[-1]==takeOut[p2]:\n",
    "                p2+=1\n",
    "                book.pop()\n",
    "        # 从p2开始\n",
    "        for i in range(p2,len(takeOut)):\n",
    "            if takeOut[i]!=book[-1]:\n",
    "                return False\n",
    "            book.pop()\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        put_idx, take_idx = 0, 0\n",
    "        stack = []\n",
    "        while put_idx < len(putIn):\n",
    "            stack.append(putIn[put_idx])\n",
    "            while len(stack) != 0 and stack[-1] == takeOut[take_idx]:\n",
    "                stack.pop()\n",
    "                take_idx += 1\n",
    "            put_idx += 1\n",
    "        return True if len(stack) == 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        j = 0\n",
    "        stack = []\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and takeOut[j] == stack[-1]:\n",
    "                stack.pop()\n",
    "                j += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        if not putIn and not takeOut:\n",
    "            return True \n",
    "        if not putIn or not takeOut:\n",
    "            return False \n",
    "        stack = []\n",
    "        for v in putIn:\n",
    "            stack.append(v)\n",
    "            while stack and takeOut and stack[-1] == takeOut[0]:\n",
    "                stack.pop()\n",
    "                takeOut.pop(0)\n",
    "        if not stack and not takeOut:\n",
    "            return True \n",
    "        else:\n",
    "            return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num) # num 入栈\n",
    "            while stack and stack[-1] == takeOut[i]: # 循环判断与出栈\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for item in putIn:\n",
    "            stack.append(item)\n",
    "            while stack and (stack[-1] == takeOut[i]):\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        q = deque()\n",
    "        cur = 0\n",
    "        for item in range(len(putIn)):\n",
    "            q.append(putIn[item])\n",
    "            while q and takeOut[cur] == q[-1]:\n",
    "                cur = cur + 1\n",
    "                q.pop()\n",
    "        return False if q else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = deque()\n",
    "        takeOut = deque(takeOut)\n",
    "\n",
    "        for item in putIn:\n",
    "            stack.append(item)\n",
    "            while len(stack) > 0 and stack[-1] == takeOut[0]:\n",
    "                stack.pop()\n",
    "                takeOut.popleft()\n",
    "        return len(stack) == 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(putIn)\n",
    "        stack = []\n",
    "        curp = curt = 0\n",
    "        while curt < n:\n",
    "            if stack and stack[-1] == takeOut[curt]:\n",
    "                stack.pop()\n",
    "                curt += 1\n",
    "                continue\n",
    "            label = False\n",
    "            while curp < n:\n",
    "                if putIn[curp] == takeOut[curt]:\n",
    "                    curp += 1\n",
    "                    curt += 1\n",
    "                    label = True\n",
    "                    break\n",
    "                stack.append(putIn[curp])\n",
    "                curp += 1\n",
    "            if not label:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            if a>b:\n",
    "                for j in range(b+1, a):\n",
    "                    if dic[putIn[j]] != -1:\n",
    "                        return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        ls = [0]*1000\n",
    "        for i in range(n):\n",
    "            ls[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            if ls[takeOut[i]]>ls[takeOut[i+1]]:\n",
    "                for j in range(ls[takeOut[i+1]]+1, ls[takeOut[i]]):\n",
    "                    if ls[putIn[j]] != -1:\n",
    "                        return False\n",
    "            ls[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        i = 1\n",
    "        putIn.insert(0, -1)\n",
    "        n = len(putIn)\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while i<n and putIn[i] != out:\n",
    "                i += 1\n",
    "            if i>=n or putIn[i]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                putIn.pop(i)\n",
    "                i -= 1\n",
    "                n -= 1\n",
    "\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        stack = [-1]\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while putIn and stack[-1] != out:\n",
    "                stack.append(putIn.pop(0))\n",
    "            if stack[-1]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                stack.pop()\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(putIn)\n",
    "        i = 0\n",
    "        stack = []\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(putIn)\n",
    "        i,j = 0,0\n",
    "        stack = []\n",
    "        while i < n and j < n:\n",
    "            stack.append(putIn[i])\n",
    "            while stack and stack[-1] == takeOut[j]:\n",
    "                stack.pop()\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putin: List[int], takeout: List[int]) -> bool:\n",
    "        n = len(putin)\n",
    "        temp = []\n",
    "        for i in range(n):\n",
    "            temp.append(putin[i])\n",
    "            while temp:\n",
    "                if temp[-1] == takeout[0]:\n",
    "                    temp.pop()\n",
    "                    takeout.pop(0)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        while temp:\n",
    "            if temp[-1] == takeout[0]:\n",
    "                temp.pop()\n",
    "                takeout.pop(0)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n=len(putIn)\n",
    "        stack=[]\n",
    "        j=0\n",
    "        for i in range (0,n):\n",
    "            stack.append(putIn[i])\n",
    "\n",
    "            while stack and stack[-1]==takeOut[j]:\n",
    "                    j+=1\n",
    "                    stack.pop()\n",
    "        return (stack==[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        seq = []\n",
    "        while putIn:\n",
    "            if putIn[0] != takeOut[0]:\n",
    "                seq.append(putIn.pop(0))\n",
    "            else:\n",
    "                putIn.pop(0)\n",
    "                takeOut.pop(0)\n",
    "                while seq:\n",
    "                    if seq[-1] == takeOut[0]:\n",
    "                        seq.pop()\n",
    "                        takeOut.pop(0)\n",
    "                    else:break\n",
    "        if takeOut:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        seq = []\n",
    "        while putIn:\n",
    "            seq.append(putIn.pop(0))\n",
    "            if seq[-1] == takeOut[0]:\n",
    "                takeOut.pop(0)\n",
    "                seq.pop()\n",
    "                while seq:\n",
    "                    if seq[-1] == takeOut[0]:\n",
    "                        seq.pop()\n",
    "                        takeOut.pop(0)\n",
    "                    else:break\n",
    "        return not takeOut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        i=j=0\n",
    "        while i<(len(putIn)) and j<len(takeOut):\n",
    "            stack.append(putIn[i])\n",
    "            while  ( stack) and (stack[-1]==takeOut[j]):\n",
    "                stack=stack[:-1]\n",
    "                j+=1\n",
    "            #else:\n",
    "            #    stack.append(putIn[i])\n",
    "            i=i+1\n",
    "        return not stack or (stack[::-1]==takeOut[j:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num) # num 入栈\n",
    "            while stack and stack[-1] == takeOut[i]: # 循环判断与出栈\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        valid_left = 0\n",
    "    \n",
    "        try:\n",
    "            for out_id in takeOut:\n",
    "                # print(f'find {out_id}, valid_left {valid_left}')\n",
    "                i = putIn.index(out_id, valid_left)\n",
    "                valid_left = i - 1 if i - 1 > 0 else 0                \n",
    "                del putIn[i]\n",
    "                # print(f'i:{i}, valid:{putIn[valid_left:]}, putIn:{putIn}')\n",
    "        except:\n",
    "            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num) # num 入栈\n",
    "            while stack and stack[-1] == takeOut[i]: # 循环判断与出栈\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stk = []\n",
    "        j = 0\n",
    "\n",
    "        for i in range(len(takeOut)):\n",
    "\n",
    "            if takeOut[i] not in stk and takeOut[i] in putIn[j:]:\n",
    "                index = putIn.index(takeOut[i])\n",
    "                for _ in range(j, index + 1):\n",
    "                    stk.append(putIn[_])\n",
    "                    j += 1\n",
    "\n",
    "            if takeOut[i] in stk:\n",
    "                while stk[-1] != takeOut[i]:\n",
    "                    stk.pop()\n",
    "                stk.pop()\n",
    "            else:\n",
    "                return False;\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack = []\n",
    "        idx = 0\n",
    "        for i in putIn:\n",
    "            stack.append(i)\n",
    "            while stack and stack[-1] == takeOut[idx]:\n",
    "                stack.pop()\n",
    "                idx += 1\n",
    "        return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: list[int], takeOut: list[int]) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and takeOut[i] == stack[-1]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        seq = []\n",
    "        while putIn:\n",
    "            if putIn[0] != takeOut[0]:\n",
    "                seq.append(putIn.pop(0))\n",
    "            else:\n",
    "                putIn.pop(0)\n",
    "                takeOut.pop(0)\n",
    "                while seq:\n",
    "                    if seq[-1] == takeOut[0]:\n",
    "                        seq.pop()\n",
    "                        takeOut.pop(0)\n",
    "                    else:break\n",
    "        return not takeOut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(putIn)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            for j in range(b+1, a):\n",
    "                if dic[putIn[j]] != -1:\n",
    "                    return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        dic = {putIn[i]:i for i in range(n)}\n",
    "            \n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            if a>b:\n",
    "                for j in range(b+1, a):\n",
    "                    if dic[putIn[j]] != -1:\n",
    "                        return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for p in putIn:\n",
    "            stack.append(p)\n",
    "            while stack and stack[-1]==takeOut[i]:\n",
    "                i += 1\n",
    "                stack.pop()\n",
    "            if stack and takeOut[i] in stack:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        ls = [0]*1000\n",
    "        for i in range(n):\n",
    "            ls[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            if ls[takeOut[i]]>ls[takeOut[i+1]]:\n",
    "                for j in range(ls[takeOut[i+1]]+1, ls[takeOut[i]]):\n",
    "                    if ls[putIn[j]] != -1:\n",
    "                        return False\n",
    "            ls[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        i = 1\n",
    "        putIn.insert(0, -1)\n",
    "        n = len(putIn)\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while i<n and putIn[i] != out:\n",
    "                i += 1\n",
    "            if i>=n or putIn[i]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                putIn.pop(i)\n",
    "                i -= 1\n",
    "                n -= 1\n",
    "\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        stack = [-1]\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while putIn and stack[-1] != out:\n",
    "                stack.append(putIn.pop(0))\n",
    "            if stack[-1]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                stack.pop()\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(putIn)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            if a>b:\n",
    "                for j in range(b+1, a):\n",
    "                    if dic[putIn[j]] != -1:\n",
    "                        return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            for j in range(b+1, a):\n",
    "                if dic[putIn[j]] != -1:\n",
    "                    return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        dic = {putIn[i]:i for i in range(n)}\n",
    "            \n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            if a>b:\n",
    "                for j in range(b+1, a):\n",
    "                    if dic[putIn[j]] != -1:\n",
    "                        return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for p in putIn:\n",
    "            stack.append(p)\n",
    "            while stack and stack[-1]==takeOut[i]:\n",
    "                i += 1\n",
    "                stack.pop()\n",
    "            if stack and takeOut[i] in stack:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        ls = [0]*1000\n",
    "        for i in range(n):\n",
    "            ls[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            if ls[takeOut[i]]>ls[takeOut[i+1]]:\n",
    "                for j in range(ls[takeOut[i+1]]+1, ls[takeOut[i]]):\n",
    "                    if ls[putIn[j]] != -1:\n",
    "                        return False\n",
    "            ls[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        i = 1\n",
    "        putIn.insert(0, -1)\n",
    "        n = len(putIn)\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while i<n and putIn[i] != out:\n",
    "                i += 1\n",
    "            if i>=n or putIn[i]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                putIn.pop(i)\n",
    "                i -= 1\n",
    "                n -= 1\n",
    "\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        stack = [-1]\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while putIn and stack[-1] != out:\n",
    "                stack.append(putIn.pop(0))\n",
    "            if stack[-1]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                stack.pop()\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num) # num 入栈\n",
    "            while stack and stack[-1] == takeOut[i]: # 循环判断与出栈\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        seq = []\n",
    "        i = 0\n",
    "        for num in putIn:\n",
    "            seq.append(num)\n",
    "            while seq and seq[-1] == takeOut[i]:\n",
    "                seq.pop()\n",
    "                i += 1\n",
    "        return not seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            # num 入栈\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                # 循环判断与出栈\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        i, j, n = 0, 0, len(putIn)\n",
    "        temp = []\n",
    "        while i < n:\n",
    "            if putIn[i] != takeOut[j]:\n",
    "                temp.append(putIn[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                i += 1\n",
    "                while temp and temp[-1] == takeOut[j]:\n",
    "                    temp.pop()\n",
    "                    j += 1\n",
    "            \n",
    "        while j < n and temp:\n",
    "            if temp[-1] == takeOut[j]:\n",
    "                temp.pop()\n",
    "                j += 1\n",
    "            else:\n",
    "                break\n",
    "        return not temp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num)\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            stack.append(num) # num 入栈\n",
    "            while stack and stack[-1] == takeOut[i]: # 循环判断与出栈\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        # 思路：\n",
    "        # 进行一次添加和弹出模拟实验，定义一个辅助栈stack，用来进行这个过程\n",
    "        # 如果到最后stack中为空，则说明putIn和takeOut的组合可以使得所有元素\n",
    "        # 完整取出\n",
    "\n",
    "        # 定义辅助栈和当前takeOut所处位置\n",
    "        stack, i = [], 0\n",
    "        for num in putIn:\n",
    "            # 将新元素无条件添加到辅助栈\n",
    "            stack.append(num)\n",
    "            # 判断是否需要弹出\n",
    "            while stack and stack[-1] == takeOut[i]:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "        return not stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        seq = []\n",
    "        while putIn:\n",
    "            seq.append(putIn.pop(0))\n",
    "            if seq[-1] == takeOut[0]:\n",
    "                takeOut.pop(0)\n",
    "                seq.pop()\n",
    "                while seq and seq[-1] == takeOut[0]:\n",
    "                    seq.pop()\n",
    "                    takeOut.pop(0)\n",
    "        return not takeOut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        n = len(putIn)\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            for j in range(b+1, a):\n",
    "                if dic[putIn[j]] != -1:\n",
    "                    return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        dic = {putIn[i]:i for i in range(n)}\n",
    "            \n",
    "        for i in range(n-1):\n",
    "            a, b = dic[takeOut[i]], dic[takeOut[i+1]]\n",
    "            if a>b:\n",
    "                for j in range(b+1, a):\n",
    "                    if dic[putIn[j]] != -1:\n",
    "                        return False\n",
    "            dic[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        i = 0\n",
    "        for p in putIn:\n",
    "            stack.append(p)\n",
    "            while stack and stack[-1]==takeOut[i]:\n",
    "                i += 1\n",
    "                stack.pop()\n",
    "            if stack and takeOut[i] in stack:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        n = len(putIn)\n",
    "        ls = [0]*1000\n",
    "        for i in range(n):\n",
    "            ls[putIn[i]] = i\n",
    "        for i in range(n-1):\n",
    "            if ls[takeOut[i]]>ls[takeOut[i+1]]:\n",
    "                for j in range(ls[takeOut[i+1]]+1, ls[takeOut[i]]):\n",
    "                    if ls[putIn[j]] != -1:\n",
    "                        return False\n",
    "            ls[takeOut[i]] = -1\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        i = 1\n",
    "        putIn.insert(0, -1)\n",
    "        n = len(putIn)\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while i<n and putIn[i] != out:\n",
    "                i += 1\n",
    "            if i>=n or putIn[i]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                putIn.pop(i)\n",
    "                i -= 1\n",
    "                n -= 1\n",
    "\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "        stack = [-1]\n",
    "        while takeOut:\n",
    "            out = takeOut.pop(0)\n",
    "            while putIn and stack[-1] != out:\n",
    "                stack.append(putIn.pop(0))\n",
    "            if stack[-1]!=out:\n",
    "                return False\n",
    "            else:\n",
    "                stack.pop()\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        chushiStack=[]\n",
    "        pos=0\n",
    "\n",
    "        for i in putIn:\n",
    "            chushiStack.append(i)\n",
    "            while chushiStack and chushiStack[-1]==takeOut[pos]:\n",
    "                print('11')\n",
    "                chushiStack.pop()\n",
    "                pos=pos+1\n",
    "        return not chushiStack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack_aux, pos = [], 0\n",
    "        for x in putIn:\n",
    "            stack_aux.append(x)\n",
    "            while stack_aux and stack_aux[-1] == takeOut[pos]:\n",
    "                stack_aux.pop()\n",
    "                pos += 1\n",
    "\n",
    "        return not stack_aux"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        i=j=0\n",
    "        while i<(len(putIn)) and j<len(takeOut):\n",
    "            while  ( stack) and (stack[-1]==takeOut[j]):\n",
    "                stack=stack[:-1]\n",
    "                j+=1\n",
    "            else:\n",
    "                stack.append(putIn[i])\n",
    "            i=i+1\n",
    "        return not stack or (stack[::-1]==takeOut[j:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        i=j=0\n",
    "        while i<(len(putIn)) and j<len(takeOut):\n",
    "            stack.append(putIn[i])\n",
    "            while  ( stack) and (stack[-1]==takeOut[j]):\n",
    "                stack=stack[:-1]\n",
    "                j+=1\n",
    "            i=i+1\n",
    "        return not stack or (stack[::-1]==takeOut[j:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:\n",
    "        j = 0\n",
    "        shelf = []\n",
    "        if len(putIn) == 0: return True\n",
    "        for i in putIn:\n",
    "            shelf.append(i)\n",
    "            while shelf[-1] == takeOut[0]:\n",
    "                shelf.pop()\n",
    "                takeOut = takeOut[1:]\n",
    "                if len(takeOut) == 0: return True\n",
    "                if len(shelf) == 0: break\n",
    "        return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
